import java.util.Arrays;
import java.util.Stack;

public class Test {

    public static void  quickSort(int[] arrary){
        quick(arrary,0,arrary.length-1);


    }
    private static void quick(int [] arrary,int start,int end){
        if (start >= end) {
            return;
        }
        int par = partitionWaken(arrary,start,end);
        quick(arrary,start,par-1);
        quick(arrary,par+1,end);
    }
    private static int partitionWaken(int [] arrary,int left,int right){
        int tmp = arrary[left];
        while (left<right){
            while (left < right && arrary[right] >= tmp){
                right--;
            }
            arrary[left] = arrary [right];
            while (left<right && arrary[left] <= tmp){
                left++;
            }
            arrary[right] = arrary[left];
        }
        arrary[left] = tmp;
        return left;
    }
    public static void quickNot(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int par = partitionWaken(array,left,right);
        if (par > left+1){
            stack.push(left);
            stack.push(par-1);

        }
        if (par < right-1){
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            par = partitionWaken(array,left,right);
            if(par > left+1){
                stack.push(left);
                stack.push(par-1);
            }
            if (par < right -1){
                stack.push(par+1);
                stack.push(right);
            }
        }
    }


    public static void main(String[] args) {

        int array [] = new int[] {1,3,44,55,66,77,545,4444,4,44,55,555,55,56,55,5,4,3,567,876,567,432,545,22456,666,5454};
        Test.quickNot(array);
        System.out.println(Arrays.toString(array));

    }
}
